﻿#pragma once
#include<iostream>
#include<map>
#include<assert.h>
#include<vector>
using namespace std;


//节点
template<class K,class V>
struct AVLtreeNode
{
	pair<K, V> _kv;             //值
	AVLtreeNode<K, V>* _left;   //左子树
	AVLtreeNode<K, V>* _right;  //右子树
	AVLtreeNode<K, V>* _parent; //父节点
	int _bf;    //平衡因子

	AVLtreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

template<class K,class V>
class AVLtree
{
	typedef AVLtreeNode<K, V> Node;
public:
	//插入
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* par = nullptr;
		//走到空
		while (cur)
		{
			//小于往左走
			if (kv.first < cur->_kv.first)
			{
				par = cur;
				cur = cur->_left;
			}
			//大于往右走
			else if (kv.first > cur->_kv.first)
			{
				par = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		//判断该插入左边还是右边
		cur = new Node(kv);
		if (kv.first < par->_kv.first)
		{
			par->_left = cur;
		}
		else
		{
			par->_right = cur;
		}
		//连接父亲节点
		cur->_parent = par;

		//更新平衡因子
		while (par != nullptr)
		{
			//左子树--
			if (par->_left == cur)
			{
				par->_bf--;
			}
			else //右子树++
			{
				par->_bf++;
			}

			if (par->_bf == 0)
			{
				//更新结束
				break;
			}
			else if (par->_bf == 1 || par->_bf == -1)
			{
				//继续向上更新
				cur = par;
				par = par->_parent;
			}
			else if (par->_bf == 2 || par->_bf == -2)
			{
				//左边不平衡,右单旋处理
				if (par->_bf == -2 && cur->_bf == -1)
				{
					//调用右单旋处理
					RotR(par);
				}
				//右边不平衡,左单旋处理
				else if (par->_bf == 2 && cur->_bf == 1)
				{
					//调用左单旋处理
					RotL(par);
				}
				else if (par->_bf == -2 && cur->_bf == 1)
				{
					//调用左右双旋处理
					RotLR(par);
				}
				else if (par->_bf == 2 && cur->_bf == -1)
				{
					//调用右左双旋处理
					RotRL(par);
				}
				else
				{
					assert(false);
				}

				break;
			}
			else
			{
				//其他数值就说明有问题，assert报错
				assert(false);
			}
		}
		return true;
	}
	//右旋转
	void RotR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		//subLR节点不为空，连接父亲节点
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		//parent上面有可能还有节点，保存parent的父亲节点
		Node* ppNode = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		//如果ppNode为空，就说明parent之前为根节点
		if (ppNode== nullptr)
		{
			//更新根节点
			_root = subL;
			//父亲节点指向空
			subL->_parent = nullptr;
		}
		else //不为空，说明还有节点
		{
			//判断ppNode连接左边还是右边
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			//ppNode给subL的父亲节点
			subL->_parent = ppNode;

		}
		parent->_bf = 0;
		subL->_bf = 0;
	}
	//左旋转
	void RotL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		//subRL节点不为空，连接父亲节点
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		//parent上面有可能还有节点，保存parent的父亲节点
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		//如果ppNode为空，就说明parent之前为根节点
		if (ppNode == nullptr)
		{
			//更新根节点
			_root = subR;
			//父亲节点指向空
			subR->_parent = nullptr;
		}
		else // //不为空，说明还有节点
		{
			//判断ppNode连接左边还是右边
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			//subL的父亲节点连接ppNode。
			subR->_parent = ppNode;
		}
		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}
	//左右双旋
	void RotLR(Node* parent)
	{
		// 1. 先保存相关节点指针
		
		// 保存parent节点的左子节点
		Node* subL = parent->_left;
		// 保存左子节点的右子节点
		Node* subLR = subL->_right;
		// 保存subLR节点的平衡因子，后续用于调整各节点的平衡因子
		int bf = subLR->_bf;
		//左单旋
		RotL(parent->_left);
		//右单旋
		RotR(parent);

		// 4. 根据subLR节点原本的平衡因子来调整parent、subL和subLR节点的平衡因子

		if (bf == -1)
		{
			// 如果subLR的平衡因子为 -1，说明其右子树较高
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;//平衡因子为0，左右子树高度平衡
		}

		else if (bf == 1)
		{
			// 如果subLR的平衡因子为1，说明其左子树较高
			parent->_bf = 0;
			// subL的平衡因子变为 -1，因为右子树相对变高
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			// 如果subL的平衡因子为0，说明subL的左右子树等高
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
			assert(false);
		}
	}
	//右左双旋
	void RotRL(Node* parent)
	{
		// 保存parent节点的右子节点
		Node* subR = parent->_right;
		// 保存右子节点的左子节点
		Node* subRL = subR->_left;
		// 保存subRL节点的平衡因子，后续用于调整各节点的平衡因子
		int bf = subRL->_bf;
		//右单旋
		RotR(parent->_right);
		//左单旋
		RotL(parent);

		if (bf == -1)
		{
			// 如果subRL的平衡因子是 -1，说明它的左子树更高
			// 旋转后，parent节点恢复平衡，平衡因子设为0
			parent->_bf = 0;
			// subR节点的右子树会相对变高，平衡因子设为1
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			// 如果subRL的平衡因子是 1，说明它的右子树更高
			// 旋转后，parent节点平衡因子设为 -1
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			// 如果subRL平衡因子是0，说明它左右子树等高
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
			assert(false);
		}
	}
	Node*  Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if(key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	void print()
	{
		zho(_root);
	}
	bool IsBalanceTree()
	{
		return  _IsBalanceTree(_root);
	}
	int Size()
	{
		return _Size(_root);
	}
	int Height()
	{
		return _Height(_root);
	}


private:

	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return 1;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;

	}


	//计算节点的平衡因子
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}


	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树 
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
 // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "⾼度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因⼦异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}

	void zho(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		zho(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		zho(root->_right);
	}

	Node* _root = nullptr;
};

